Hodowla

Limit pamięci: 32 MB

Bajtocki ogród działkowy (BOD) od wielu lat hoduje warzywa - wyłącznie marchewki i pietruszki. BOD ma kształt kwadratu o boku długości i jest podzielony na jednostkowych pól. Na każdym z nich rośnie dokładnie jedna marchewka lub jedna pietruszka.

Specjalna hodowla decyduje o wyjątkowości i smaku warzyw. Polega ona na corocznym wybieraniu pewnego obszaru, dla którego dokonujemy zamiany hodowli. Zamiana hodowli polega na posadzeniu marchewek wszędzie tam, gdzie rosły dotąd pietruszki, a pietruszek wszędzie tam, gdzie rosły marchewki. Na pozostałym obszarze marchewki i pietruszki rosną dokładnie tam, gdzie rok temu.

Właściciel ogrodu rozpisał plan hodowli na wiele lat. Zastanawia się teraz, jak będzie wyglądał jego ogród działkowy po tych wszystkich latach.

Wejście

Pierwszy wiersz standardowego wejścia zawiera jedną liczbę całkowitą (), oznaczającą rozmiar ogrodu działkowego. W kolejnych wierszach znajduje się opis działki.

Każdy wiersz opisuje jeden pas ogrodu i zawiera liczb całkowitych , (), gdzie opisuje -te pole w rozpatrywanym pasie działki. Jeśli jest równe 0, to na polu tym rośnie marchewka, jeśli natomiast jest równe 1, to rośnie tam pietruszka.

Kolejny wiersz wejścia zawiera jedną liczbę całkowitą (), oznaczającą liczbę lat, dla których właściciel rozpisał plan hodowli. W następnych wierszach znajduje się opis zamian hodowli w kolejnych latach.

Każdy wiersz zawiera cztery liczby całkowite (), oznaczające, że w danym roku właściciel planuje dokonać zamiany hodowli na polach wyznaczonych przez prostokąt, ktorego lewy górny róg posiada współrzędne , a prawy dolny róg . W testach wartych około punktów zachodzą dodatkowe warunki .

Wyjście

Standardowe wyjście powinno zawierać wierszy. Każdy wiersz powinien opisywać kolejny pas działki po latach i powinien zawierać liczb całkowitych , gdzie powinno być równe 1 - jeśli na tym polu rosnąć będzie marchewka lub 0 - jeśli pietruszka.

Przykład

Dla danych wejściowych:

4
1 1 0 1
0 0 1 0
1 0 1 1
0 1 0 1
2
3 1 4 3
2 3 3 4

poprawną odpowiedzią jest:

1 1 1 0 
0 0 0 1 
1 1 1 0 
0 0 1 1 

Autor zadania: Jacek Tomasiewicz.